[luogu 3254] 圆桌问题

原题链接:[luogu 3254] 圆桌问题
题目大意:有$m$个单位派出若干个代表参加一场会议,第$i$个单位派出了$r_i$个人.一共有$n$个餐桌,每个餐桌上可以坐$c_i$个人.要求每个桌子上坐的代表来自不同的单位.求出是否存在一种方案使得上条件满足,如果能,输出具体方案.如果不能输出$0$.

数据范围:
$1 \leq m \leq 150$
$1 \leq n \leq 270$
$1 \leq r_i,c_i \leq 10^3$

先想办法把这个题的图建出来:首先对单位和桌子之间考虑,显然每个单位只能对每个桌子派出一个人,那么单位与桌子之间的连边每个边的容量就应该是设置成$1$.连完之后这张图很显然是一张二分图,原问题的答案就是求这个二分图的多重匹配,这个如果用匈牙利做的话要拆点.因为对每个单位来说,他要派出去$r_i$个人到$r_i$个不同的桌子上去,而匈牙利不能直接说去多次匹配一个点,他得把每个点拆成多个点,再对他做匹配.但是网络流可以不拆点,因为你把左边的所有点都连向一个源点$S$的话,每个边的流量是$r_i$之后,如果走的是一个最大流,那么每条边都应该走到最大,也就是走了$r_i$出去,中间的单位和边的边不储存流量,而且只走一个人,也就是$1$的容量.最后就是一个汇点问题,跟源点的建立也是对称的,因为每个桌子最多坐$c_i$个人,那么显然就是每个桌子往汇点连一条容量为$c_i$的边.
整个过程可以这么理解:从每个单位点到每个桌子,肯定是连一条边,这里的整张图一定是一个二分图.其次你得让每个单位来$r_i$个人,每个桌子坐$c_i$个人,这两个条件分别就是源点走单位点,容量是$r_i$;而桌子点走汇点,容量是$c_i$.假设说最大流跑满了的话,从源点出去的所有流量应该都是跑满的,到达汇点的所有流量应该都是占满了$c_i$的.换句话说如果最大流就是$\sum r_i$的话,就说明所有的单位里的人都找到一个不同的位置坐.这就是题目判断是否坐满了的条件.也就是说这样处理了之后,新的网络上跑最大流等价于原来的二分图上跑多重匹配,因此是正确的.
分析到这里,这个题就没什么问题了,不过还要输出方案:先遍历所有的边,找到这条边联通的两个点,如果这两个点不是源点或者汇点的话,就再看反向边的流量是不是$1$,如果是的话说明这条边被用了,也就是说找到应该是左部的点$u$,之后再把另外一点$v$加入到答案集合里.最后一起输出即可.
不过对于实际建图的时候,我的代码里先把所有的桌子的$id$映射成了$j + m$所以实际的答案里,他们的$id$还需要重新映射回去,变成$j$才行,这一点需要注意一下.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500,M = 1e6+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],pre[N];
ll incf[N],maxflow;
queue<int> q;
vector<int> res[N];
void add(int u,int v,int w)
{
	edge[++idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx; 
	
	edge[++idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx;
}
bool bfs()
{
	memset(d,0,sizeof d);
	while(q.size())	q.pop();
	q.push(s);d[s] = 1;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q.push(v);
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
	if(u == t)	return flow;
	int rest = flow,k,i;
	for(int i = ver[u];i && rest;i = succ[i])
	{
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(rest,cap[i]));
			if(!k)	d[v] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}
int main()
{
	scanf("%d%d",&m,&n);
	s = 0;t = n + m + 2;
	int sump = 0;
	for(int i = 1;i <= m;++i)
	{
		int x;scanf("%d",&x);
		sump += x;
		add(s,i,x);
	}
	for(int i = 1;i <= m;++i)
		for(int j = 1;j <= n;++j)
			add(i,j + m,1);
	for(int i = 1;i <= n;++i)
	{
		int x;scanf("%d",&x);
		add(i + m,t,x);
	}
	int flow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
    if(maxflow != sump)	printf("0");
    else
    {
    	printf("1\n");
		for(int i = 2;i <= idx;i += 2)
		{
			int u = edge[i ^ 1],v = edge[i];
			if(u == s || u == t || v == s || v == t)	continue;
			if(cap[i ^ 1])
				res[u].push_back(v - m);
		}
		for(int i = 1;i <= m;++i)
		{
			for(auto& j : res[i])
				printf("%d ",j);
			puts("");
		}
    }
    return 0;
}